import java.util.*;

/**
* @description: 947. 移除最多的同行或同列石头
* @author hewei
* @date 2022/8/15 14:49
* @version 1.0
*/

public class RemoveStones {

    public int removeStones1(int[][] stones) {
        HashMap<Integer, List<Integer>> leftMap = new HashMap<>();
        HashMap<Integer, List<Integer>> rightMap = new HashMap<>();
        for (int i = 0; i < stones.length; i++) {
            int x = stones[i][0];
            int y = stones[i][1];
            leftMap.computeIfAbsent(x, k -> new ArrayList<>());
            rightMap.computeIfAbsent(y, k -> new ArrayList<>());
            leftMap.get(x).add(i);
            rightMap.get(y).add(i);
        }
        int ans = 0;
        Deque<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < stones.length; i++) {
            if (set.contains(i)) continue;
            queue.add(i);
            set.add(i);
            int count = 0;
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                int x = stones[poll][0];
                int y = stones[poll][1];
                for (Integer index : leftMap.get(x)) {
                    if (!set.contains(index)) {
                        queue.push(index);
                        set.add(index);
                    }
                }
                for (Integer index : rightMap.get(y)) {
                    if (!set.contains(index)) {
                        queue.push(index);
                        set.add(index);
                    }
                }
                ++count;
            }
            ans += count - 1;
        }
        return ans;
    }

    public int removeStones(int[][] stones) {
        Union union = new Union(200001);
        for (int i = 0; i < stones.length; i++) {
            union.union(stones[i][0], stones[i][1] + 10000);
        }
        return stones.length - union.count;
    }

    class Union {
        int[] parents;
        int count;
        public Union(int n) {
            parents = new int[n];
            Arrays.fill(parents, -1);
            count = 0;
        }

        public int find(int i) {
            if (parents[i] == -1) {
                ++count;
                parents[i] = i;
            }

            while (parents[i] != i) {
                parents[i] = parents[parents[i]];
                i = parents[i];
            }
            return i;
        }

        public void union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x == y) return;
            parents[y] = x;
            --count;
        }
    }
}
